Tic-tac-toe

Tic-tac-toe

Game play of Tic-tac-toe
Genre(s) Paper and pencil game
Players 2
Setup time Minimal
Playing time ~1 min
Random chance None
Skill(s) required Strategy

Tic-tac-toe, also called noughts and crosses (in the UK, Australia, New Zealand, South Africa, India and the rest of the British Commonwealth countries), is a pencil-and-paper game for two players, X and O, who take turns marking the spaces in a 3×3 grid. The X player usually goes first. The player who succeeds in placing three respective marks in a horizontal, vertical, or diagonal row wins the game.

The following example game is won by the first player, X:

Players soon discover that best play from both parties leads to a draw (often referred to as cat or cat's game). Hence, tic-tac-toe is most often played by young children.

The friendliness of tic-tac-toe games makes them ideal as a pedagogical tool for teaching the concepts of good sportsmanship and the branch of artificial intelligence that deals with the searching of game trees. It is straightforward to write a computer program to play tic-tac-toe perfectly, to enumerate the 765 essentially different positions (the state space complexity), or the 26,830 possible games up to rotations and reflections (the game tree complexity) on this space.

Contents

History

An early variant of Tic-tac-toe was played in Roman Empire, around the first century BC. It was called Terni Lapilli and instead of having any number of pieces, each player only had three, thus they had to move them around to empty spaces to keep playing. The game's grid markings have been found chalked all over Rome.

However, according to Claudia Zaslavsky's book Tic Tac Toe: And Other Three-In-A Row Games from Ancient Egypt to the Modern Computer, Tic-Tac-Toe could originate back to ancient Egypt.[1]

The different names of the game are more recent. The first print reference to "noughts and crosses", the British name, appeared in 1864. The first print reference to a game called "tick-tack-toe" occurred in 1884, but referred to "a children's game played on a slate, consisting in trying with the eyes shut to bring the pencil down on one of the numbers of a set, the number hit being scored". "Tic-tac-toe" may also derive from "tick-tack", the name of an old version of backgammon first described in 1558. The U.S. renaming of noughts and crosses as tic-tac-toe occurred in the 20th century.[2]

In 1952, Tic-tac-toe became the first known video game, OXO (or Noughts and Crosses) for the EDSAC computer. The computer player could play perfect games of tic-tac-toe against a human opponent.

In 1975, Tic-Tac-Toe was also used by MIT students to demonstrate the computational power of Tinkertoy elements. The Tinkertoy computer, made out of (almost) only Tinkertoys, is able to play Tic-Tac-Toe perfectly[3]. It is currently on display at the Museum of Science, Boston.

Combinatorics

Despite its apparent simplicity, Tic-tac-toe requires detailed analysis to determine even some elementary combinatory facts, the most interesting of which are the number of possible games and the number of possible positions. A position is merely a state of the board, while a game usually refers to the way a terminal position is obtained.

A naive count of the number of positions leads to 19,683 possible board layouts (39 since each of the nine spaces can be X, O or blank), and a similar count of the number of games leads to 362,880 (i.e. 9!) different sequences for placing the Xs and Os on the board. However, this doesn't take into account the fact that the game ends when three-in-a-row is obtained. Many of the 19,683 positions are unreachable in an actual game.

The complete analysis is further complicated by the definitions used when setting the conditions, like board symmetries.

Number of terminal positions

When considering only the state of the board, and after taking into account board symmetries (i.e. rotations and reflections), there are only 138 terminal board positions. Assuming that X makes the first move every time:

Number of possible games

Without taking symmetries into account, the number of possible games can be determined by hand with an exact formula that leads to 255,168 possible games (see Henry Bottomley, 2001[4], or Steve Schaeffer, 2002[5]). Assuming that X makes the first move every time:

If board symmetries are taken into account, two games are considered the same if the sequence of board modulo the symmetries is the same. With the use of computer, Steve Schaeffer determined in 2002[5] that the number of games in these conditions is 26,830.

Strategy

A player can play perfect tic-tac-toe (win or draw) given they move according to the highest possible move from the following table.[7]

  1. Win: If the player has two in a row, play the third to get three in a row.
  2. Block: If the [opponent] has two in a row, play the third to block them.
  3. Fork: Create an opportunity where you can win in two ways.
  4. Block opponent's Fork:
    • Option 1: Create two in a row to force the opponent into defending, as long as it doesn't result in them creating a fork or winning. For example, if "X" has a corner, "O" has the center, and "X" has the opposite corner as well, "O" must not play a corner in order to win. (Playing a corner in this scenario creates a fork for "X" to win.)
    • Option 2: If there is a configuration where the opponent can fork, block that fork.
  5. Center: Play the center.
  6. Opposite corner: If the opponent is in the corner, play the opposite corner.
  7. Empty corner: Play in a corner square.
  8. Empty side: Play in a middle square on any of the 4 sides.

The first player, whom we shall designate "X", has 3 possible positions to mark during the first turn. Superficially, it might seem that there are 9 possible positions, corresponding to the 9 squares in the grid. However, by rotating the board, we will find that in the first turn, every corner mark is strategically equivalent to every other corner mark. The same is true of every edge mark. For strategy purposes, there are therefore only three possible first marks: corner, edge, or center. Player X can win or force a draw from any of these starting marks; however, playing the corner gives the opponent the smallest choice of squares which must be played to avoid losing.[8]

The second player, whom we shall designate "O", must respond to X's opening mark in such a way as to avoid the forced win. Player O must always respond to a corner opening with a center mark, and to a center opening with a corner mark. An edge opening must be answered either with a center mark, a corner mark next to the X, or an edge mark opposite the X. Any other responses will allow X to force the win. Once the opening is completed, O's task is to follow the above list of priorities in order to force the draw, or else to gain a win if X makes a weak play.

To guarantee a tie if you're O though, if X doesn't play center (playing a corner is the best opening move), take center, and then a side middle. This will stop any forks from happening. If you play a corner, a perfect X player has already played the corner opposite his first and proceeds to play a 3rd corner, stopping your 3-in-a-row and making his own fork. If X plays center opening move, just keep your eyes open and he won't be able to fork you. If you are X, play a corner first. If O takes center (best move for him), take the corner oppsotie your original, and proceed as detailed above. If O plays a corner or side-middle first, you are guaranteed to win. If corner, simply take any of the other 2 corners, and then the last. You've forked him. If he plays a side-middle, take the only corner that his blocking won't make 2 in a row. he'll block, but the best of the other two, you'll see which one, and you'll fork him. The only way for X not to win is for O to play middle and then a side-middle.

Variations

Many board games share the element of trying to be the first to get n-in-a-row: three men's morris, nine men's morris, pente, gomoku, Qubic, Connect Four, Quarto, Gobblet. Generalizing the original Tic-tac-toe game, we get the n^d-game, played on the d-dimensional cube with edge n.[9] Then, the ordinary Tic-tac-toe is the 3^2-game. The m,n,k-games are a family of generalized games based on tic-tac-toe.

Alternative English names

The game has a number of alternative English names.

In the United States, the name "noughts and crosses" is not well understood, as the word "nought" is archaic in usage and X-shaped objects are not generally called crosses except in the case of specific named crosses like St. Patrick's Cross.

Sometimes, the games Tic-tac-toe (where players keep adding "pieces") and Three Men's Morris (where pieces start to move after a certain number have been placed) are confused with each other.

In popular culture

In the 1983 film WarGames, tic-tac-toe is used as an allegory for nuclear war. In the climax of the film, the protagonist prevents an out of control military defense computer from launching nuclear missiles by making it repeatedly play tic-tac-toe against itself. After quickly learning that good strategy by both players produces no winner, the computer then plays through all known nuclear strike scenarios, again finding no winner. The computer concludes, "Strange game. The only winning move is not to play."

Various game shows have been based on Tic-Tac-Toe and its variants:

See also

References

  1. ^ Zaslavsky, Claudia (1982). Tic Tac Toe: And Other Three-In-A Row Games from Ancient Egypt to the Modern Computer. Crowell. ISBN 0690043163. http://www.jacketflap.com/bookdetail.asp?bookid=0690043163. 
  2. ^ Oxford English Dictionary entries for "Noughts and Crosses", "Tick-Tack" and "Tick-Tack-Toe", dictionary.oed.com
  3. ^ "Tinkertoys and tic-tac-toe". http://www.rci.rutgers.edu/~cfs/472_html/Intro/TinkertoyComputer/TinkerToy.html. Retrieved 2007-09-27. 
  4. ^ How many Tic-Tac-Toe games are possible? Henry Bottomley, 2001
  5. ^ a b Mathematical Recreations Steve Schaeffer, 2002
  6. ^ Based on an image published by Randall Munroe on xkcd
  7. ^ Kevin Crowley, Robert S. Siegler (1993). "Flexible Strategy Use in Young Children’s Tic-Tac-Toe". Cognitive Science 17 (4): 531–561. doi:10.1016/0364-0213(93)90003-Q. 
  8. ^ Martin Gardner (1988). Hexaflexagons and Other Mathematical Diversions. University of Chicago Press. 
  9. ^ J. Beck: Combinatorial Games: Tic-Tac-Toe Theory, Cambridge University Press, 2008.
  10. ^ Oren Patashnik, Qubic: 4 x 4 x 4 Tic-Tac-Toe, Mathematical Magazine 53 (1980) 202–216.
  11. ^ Goff, Allan (November 2006). "Quantum tic-tac-toe: A teaching metaphor for superposition in quantum mechanics". American Journal of Physics (College Park, MD: American Association of Physics Teachers) 74 (11): 962–973. doi:10.1119/1.2213635. ISSN 0002-9505. 

External links